Propriété caractéristique du PGCD

Propriété

Soit $a\in \mathbb{Z}$ et $b\in \mathbb{Z}$ non nuls. Soit $d\in {\mathbb{N}}^{\ast }$ .

On a  $d=\mathrm{PGCD}(a;b)$  si, et seulement si, il existe $(a^{\prime };b^{\prime })\in {\mathbb{Z}}^2$ tel que $\{\begin{array}{l}a=a^{\prime }d\\ b=b^{\prime }d\\ \mathrm{PGCD}(a^{\prime };b^{\prime })=1.\end{array}$  

Démonstration

On procède par double implication.

$[\Rightarrow ]$ On suppose que $d=\mathrm{PGCD}(a;b)$ .
Ainsi  $d$ divise $a$ et $b$ , donc il existe $(a^{\prime };b^{\prime })\in {\mathbb{Z}}^2$ tel que $a=a^{\prime }d$ et $b=b^{\prime }d$ .
De plus, comme $d>0$ , 
$\begin{array}{r}d=\mathrm{PGCD}(a;b)=\mathrm{PGCD}(a^{\prime }d;b^{\prime }d)=d\times \mathrm{PGCD}(a^{\prime };b^{\prime })\end{array}$  
et donc, en simplifiant par $d$ , on a $\mathrm{PGCD}(a^{\prime };b^{\prime })=1$ .

$[\Leftarrow ]$ On suppose qu'il existe $(a^{\prime };b^{\prime })\in {\mathbb{Z}}^2$ tel que $a=a^{\prime }d$ , $b=b^{\prime }d$ et $\mathrm{PGCD}(a^{\prime };b^{\prime })=1$ .
On a alors, comme $d>0$ , 
$\begin{array}{r}\mathrm{PGCD}(a;b)=\mathrm{PGCD}(a^{\prime }d;b^{\prime }d)=d\times \mathrm{PGCD}(a^{\prime };b^{\prime })=d\times 1=d\end{array}$  
et donc $d=\mathrm{PGCD}(a;b)$ .